/**
 * @author LKQ
 * @date 2022/2/22 18:56
 * @description 方法一：HashSet，但是需要额外空间；
 * 方法二：排序，但是会修改原数组
 * 方法三：计数排序，同样需要额外空间
 * 解决办法1：Floyd判圈算法，也即快慢指针。由题意得，只有一个整数出现多次，那么i-> nums[i], 将会存在环。
 *
 */
public class FormalSolution {
    public static void main(String[] args) {

    }
    public int findDuplicate(int[] nums) {
        int slow = 0, fast = 0;
        do {
            // 慢指针每次走一步，快指针每次走两步
            slow = nums[slow];
            fast = nums[nums[fast]];
        }while (slow != fast);
        // 当相遇时，慢指针回到起点
        slow = 0;
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        // 再次相遇时，即为环的入口点。
        return slow;
    }
}
